﻿
#ifndef _MISC_H_
#define _MISC_H_

#include <climits>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>
#include <set>
#include <string>
#include <cstdlib>
#include <ctime>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class RemoveNthNodeFromEndOfList {
    /*
    Given a linked list, remove the nth node from the end of list and return its head.
    For example,

       Given linked list: 1->2->3->4->5, and n = 2.

       After removing the second node from the end, the linked list becomes 1->2->3->5.
    Note:
    Given n will always be valid.
    Try to do this in one pass.
    */
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //It's not a good idea to use vector to store all pointers
        /*if (n == 0)
        {
            return head;
        }
        vector<ListNode*> node_list;
        while (head != nullptr)
        {
            node_list.push_back(head);
            head = head->next;
        }
        int ss = node_list.size();
        int node_n = ss - n;
        if (node_n < 0)
        {
            return node_list[0];
        }
        if (node_n == 0)
        {
            return node_list[node_n]->next;
        }
        node_list[node_n-1]->next = node_list[node_n]->next;
        return node_list[0];*/
        ListNode *first = head;
        ListNode *second = head;
        ListNode *prev = first;
        while (n--)
        {
            second = second->next;
        }
        while (second != nullptr)
        {
            second = second->next;
            prev = first;
            first = first->next;
        }
        if (first == head)
        {
            return first->next;
        }
        prev->next = first->next;
        return head;
    }
};

class ThreeSum {
    /*
    Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

    Note: The solution set must not contain duplicate triplets.

    For example, given array S = [-1, 0, 1, 2, -1, -4],

    A solution set is:
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]
    */
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        std::sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); ++i)
        {
            // There is a key question here! Why we could use the first smaller number to be the target?
            // How could this be always solvable by iterating the 'nums' vector in this way?
            // That's not so intuitive, however, suppose we set i element as the target, and we could find
            // some index p, q where nums[i] + nums[p] + nums[q] = 0, and p < i or q < i, however, we have already
            // solve all the subproblem where the target index j lower than i, the subproblem is:
            // target is elements j(min(i, p, q)), and we have already found all the results  with j, one is
            // i, p, q, so when we iterate the index from 0 to nums.size(), we do not need to take care of the lower one anymore.
            int target = -nums[i];
            size_t front = i + 1;
            size_t end = nums.size() - 1;
            while (front < end)
            {
                int data = nums[front] + nums[end];
                if (data < target)
                {
                    ++front;
                }
                else if (data > target)
                {
                    --end;
                }
                else
                {
                    vector<int> sol;
                    sol.push_back(nums[i]);
                    sol.push_back(nums[front]);
                    sol.push_back(nums[end]);
                    res.push_back(sol);
                    while (nums[front] == sol[1])
                    {
                        ++front;
                    }
                    while (nums[end] == sol[2])
                    {
                        --end;
                    }
                }
            }
            while ((i + 1) < nums.size() && nums[i+1] == nums[i])
            {
                ++i;
            }
        }
        return res;
    }
};

class LetterConbinationOfPhoneNumberBackTracking {
    /*
    Given a digit string, return all possible letter combinations that the number could represent.

    A mapping of digit to letters (just like on the telephone buttons) is given below.

    {0: "", 1: "", 2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz"}

    Input:Digit string "23"
    Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
    Note:
    Although the above answer is in lexicographical order, your answer could be in any order you want.
    
    BackTracking recursive solution.
    */
    public:
    vector<string> letterCombinations(string digits) {
        static const vector<string> num_vec = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> res;
        if (digits.size() == 0) {
            return res;
        }
        string tmp_res;
        backTracking(0, digits, num_vec, tmp_res, res);
        return res;
    }
    void backTracking(int current_idx, string &digits, const vector<string>& num_vec, string &tmp_res, vector<string>& res) {
        if (current_idx == digits.size()) {
            res.push_back(tmp_res);
        }
        else {
            string num = num_vec[digits[current_idx] - '0'];
            for (int i = 0; i < num.size(); ++i) {
                tmp_res.push_back(num[i]);
                backTracking(current_idx+1, digits, num_vec, tmp_res, res);
                tmp_res.pop_back();
            }
        }
    }
};

class LetterConbinationOfPhoneNumberParallel {
    /*
    Given a digit string, return all possible letter combinations that the number could represent.

    A mapping of digit to letters (just like on the telephone buttons) is given below.

    {0: "", 1: "", 2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz"}

    Input:Digit string "23"
    Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
    Note:
    Although the above answer is in lexicographical order, your answer could be in any order you want.
    
    This question may be solved by backtracking, however, we could also use STL vector to parallelly
    calculate all the results at the same time. That is quite skillfully.
    Generally speaking, all the recusive problem could be solved by using loop.
    However, I still do know how to convert all the recursive problem into looping.
    */
public:
    vector<string> letterCombinations(string digits) {
        // It's quite a good idea to store all the map from number to string into an vector in C++
        static const vector<string> num_vec = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> res;
        if (digits.size() == 0) {
            return res;
        }
        res.push_back("");
        for (int i = 0; i < digits.size(); ++i) {
            if (digits[i] < '0' || digits[i] > '9') {
                continue;
            }
            int digit = digits[i] - '0';
            string num = num_vec[digit];
            if (num.size() == 0) {
                continue;
            }
            // creat a new temporary vector to compute all the result at the same time
            vector<string> tmp;
            for (int j = 0; j < res.size(); ++j) {
                for (int k = 0; k < num.size(); ++k) {
                    tmp.push_back(res[j] + num[k]);
                }
            }
            res = tmp;
        }
        return res;
    }
};

class GenerateParentheses {
    /*
    Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

    For example, given n = 3, a solution set is:

    [
      "((()))",
      "(()())",
      "(())()",
      "()(())",
      "()()()"
    ]
    This is a typical backtracking problem.
    */
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        if (n <= 0) {
            return res;
        }
        string tmp_res = "";
        backTracking(n, tmp_res, n * 2, res, 0);
        return res;
    }
    void backTracking(int current_idx, string tmp_res, const int& total_size, vector<string>& res, int left_para) {
        if (current_idx == 0) {
            while (tmp_res.size() < total_size) {
                tmp_res.push_back(')');
            }
            res.push_back(tmp_res);
        }
        else {
            tmp_res.push_back('(');
            ++left_para;  // key point of this question is to store current left un closed parathesis while backtracking
            backTracking(current_idx - 1, tmp_res, total_size, res, left_para);
            tmp_res.pop_back();
            --left_para;
            if (left_para != 0) {
                tmp_res.push_back(')');
                --left_para;
                backTracking(current_idx, tmp_res, total_size, res, left_para);
            }
        }
    }
};


class GenerateParenthesesStackVersion
{
public:
    vector<string> generateParenthesis(int n) {
        if (n == 0) return {};
        vector<string> res;
        //generate(res, 0, n, "");
        
        stack<pair<int, string>> st;
        string val = "";
        for (int i = 0; i < n; ++i) {
            val += '(';
            st.push(make_pair(i+1, val));
        }
        
        while (!st.empty()) {
            pair<int, string> is = st.top(); st.pop();
            val = is.second;
            if (is.first == n) {
                while (val.size() < 2*n) val += ')';
                res.push_back(val);
            } else {
                int left_b = is.first;
                if (left_b * 2 > val.size()) {
                    val += ')';
                    if (val.size() < left_b * 2) st.push(make_pair(left_b, val));
                }
                while (left_b < n) {
                    ++left_b;
                    val += '(';
                    st.push(make_pair(left_b, val));
                }
            }
        }
        
        return res;
    }
    
    /*void generate(vector<string>& res, int left_branch, int& n, string val) {
        if (left_branch == n) {
            int s = n * 2;
            while (val.size() != s) {
                val.push_back(')');
            }
            res.push_back(val);
        } else {
            generate(res, left_branch + 1, n, val + '(');
            if (left_branch > 0 && val.size() < 2*left_branch) {
                generate(res, left_branch, n, val + ')');
            }
        }
    }*/
};


class TestGenerateParenthesesStackVersion : public testing::Test
{

};


TEST_F(TestGenerateParenthesesStackVersion, GPS1) {
    auto gps1 = new GenerateParenthesesStackVersion();
    vector<string> res = gps1->generateParenthesis(3);
    delete gps1;
}


class MergeKLists {
/**
 * Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
public:
    struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) {
            return nullptr;
        }
        /*ListNode *head = lists[0];
        for (int i = 1; i < lists.size(); ++i) {
            head = mergeTwoSortedList(head, lists[i]);
        }
        return head;*/
        // in-place merge, however, little bit faster than the previous one
        //ListNode *head = lists[0];
        size_t len = lists.size();
        size_t interval = 1;
        while (interval < len) {
            for (size_t i = 0; (i + interval) < lists.size(); i += 2*interval) {
                lists[i] = mergeTwoSortedList(lists[i], lists[i+interval]);
            }
            interval *= 2;
        }
        return lists[0];
    }
    ListNode* mergeTwoSortedList(ListNode* l1, ListNode *l2) {
        if (l1 == nullptr) {
            return l2;
        }
        if (l2 == nullptr) {
            return l1;
        }
        ListNode *head;
        if (l1->val < l2->val) {
            head = l1;
            l1 = l1->next;
        }
        else {
            head = l2;
            l2 = l2->next;
        }
        ListNode *tmp = head;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                tmp->next = l1;
                tmp = tmp->next;
                l1 = l1->next;
            }
            else {
                tmp->next = l2;
                tmp = tmp->next;
                l2 = l2->next;
            }
        }
        if (l1 != nullptr) {
            tmp->next = l1;
        }
        else if (l2 != nullptr) {
            tmp->next = l2;
        }
        return head;
    }
};

class NextPermutation {
/*
    Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

    If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

    The replacement must be in-place, do not allocate extra memory.

    Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
    1,2,3 → 1,3,2
    3,2,1 → 1,2,3
    1,1,5 → 1,5,1
 */
public:

    void nextPermutation(vector<int>& nums) {
        int last_dec_idx = -1;
        size_t i;
        // from end to start, find the first decrease element
        for (i = nums.size() - 1; i > 0; --i) {
            if (nums[i-1] < nums[i]) {
                last_dec_idx = (int)(i-1);
                break;
            }
        }
        if (last_dec_idx == -1) {
            // nums is completely in descendent order
            swapOrder(nums, 0, nums.size() - 1);
        }
        else {
            size_t next_elem_idx = -1;
            int diff = INT_MAX, tmp_diff;
            // find the next closest elem which diff > 0
            for (i = last_dec_idx + 1; i < nums.size(); ++i) {
                tmp_diff = nums[i] - nums[last_dec_idx];
                if (tmp_diff > 0 && diff >= tmp_diff) {
                    diff = tmp_diff;
                    next_elem_idx = i;
                }
                //if (nums[i] == (nums[last_dec_idx] + 1)) {
                //    next_elem_idx = i;
                //    break;
                //}
            }
            int tmp;
            tmp = nums[next_elem_idx];
            nums[next_elem_idx] = nums[last_dec_idx];
            nums[last_dec_idx] = tmp;
            swapOrder(nums, last_dec_idx + 1, nums.size() - 1);
        }
    }
    void swapOrder(vector<int>& nums, size_t start_idx, size_t end_idx) {
        int tmp;
        while (start_idx < end_idx) {
            tmp = nums[start_idx];
            nums[start_idx] = nums[end_idx];
            nums[end_idx] = tmp;
            ++start_idx;
            --end_idx;
        }
    }
};

class MedianOfTwoArray {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        size_t size1 = nums1.size();
        size_t size2 = nums2.size();
        vector<int>& A = size1 < size2 ? nums1 : nums2;
        vector<int>& B = size1 < size2 ? nums2 : nums1;
        size_t m = min(size1, size2);
        size_t n = max(size1, size2);
        size_t iMin = 0, iMax = m, i, j;
        size_t half_len = (m + n + 1) / 2, max_of_left, min_of_right;
        while (iMin <= iMax) {
            i = (iMax + iMin) / 2;
            j = half_len - i;
            if (i < iMax && A[i] < B[j - 1]) {
                iMin =  i + 1;
            } else if (i > iMin && A[i - 1] > B[j]) {
                iMax = i - 1;
            } else {
                if (i == 0) max_of_left = B[j - 1];
                else if (j == 0) max_of_left = A[i - 1];
                else max_of_left = max(A[i - 1], B[j - 1]);
                
                if ((m + n) % 2 == 1)
                    return static_cast<double>(max_of_left);
                
                if (i == m) min_of_right = B[j];
                else if (j == n) min_of_right = A[i];
                else min_of_right = min(A[i], B[j]);
                return (max_of_left + min_of_right) / 2.0;
            }
        }
        return 0.0;
    }
};

class RegExpMatcher {
public:
    bool isMatch(string s, string p)
    {
        if (p.empty())  // when the pattern is empty, we don't need to match any more!
        {
            return s.empty();
        }
        // when s is empty, we still need to match the left pattern.
        bool is_match = !s.empty() && (s[0] == p[0] || p[0] == '.');
        if (p.size() >= 2 && p[1] == '*')
        {
            return isMatch(s, p.substr(2)) || is_match && isMatch(s.substr(1), p);
        }
        else
        {
            return is_match && isMatch(s.substr(1), p.substr(1));
        }
    }
};

class MemRegExpMatcher {
    // It's not so fast to use map indeed!
    map<pair<string, string>, bool> _mem;  // it's not a good idea to cache all the string appear!!!
    typedef pair<string, string> _pair;
public:
    bool isMatch(string s, string p)
    {
        if (p.empty())  // when the pattern is empty, we don't need to match any more!
        {
            return s.empty();
        }
        _pair sp(s, p);
        if (_mem.find(sp) != _mem.end())
        {
            return _mem[sp];
        }
        // when s is empty, we still need to match the left pattern.
        bool res;
        bool is_match = !s.empty() && (s[0] == p[0] || p[0] == '.');
        if (p.size() >= 2 && p[1] == '*')
        {
            res = isMatch(s, p.substr(2)) || is_match && isMatch(s.substr(1), p);
        }
        else
        {
            res = is_match && isMatch(s.substr(1), p.substr(1));
        }
        _mem[sp] = res;
        return res;
    }
};

class DPRegExpMatcher {
    // Forward dynamic programming
public:
    bool isMatch(string s, string p)
    {
        size_t ss = s.size();
        size_t ps = p.size();
        bool **match_arr = new bool*[ss + 1];
        size_t i, j;
        for (i = 0; i < ss + 1; ++i)
        {
            match_arr[i] = new bool[ps + 1];
        }
        for (i = 0; i < ss + 1; ++i)
        {
            for (j = 0; j < ps + 1; ++j)
            {
                match_arr[i][j] = false;
            }
        }

        //match_arr[i][j]: whether s[0:i-1] match p[0:j-1]
        match_arr[0][0] = true;
        for (j = 1; j < ps + 1; ++j)
        {
            match_arr[0][j] = j >= 2 && p[j - 1] == '*' && match_arr[0][j - 2];
        }
        for (i = 1; i < ss + 1; ++i)
        {
            for (j = 1; j < ps + 1; ++j)
            {
                if (p[j - 1] != '*')
                {
                    match_arr[i][j] = match_arr[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
                }
                else
                {
                    match_arr[i][j] = j >= 2 && (match_arr[i][j - 2] || (match_arr[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.')));
                }
            }
        }
        bool res = match_arr[ss][ps];
        for (i = 0; i < ss + 1; ++i)
        {
            delete[] match_arr[i];
        }
        delete[] match_arr;
        return res;
    }
};

/* https://leetcode-cn.com/problems/burst-balloons/description/
Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note: 
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

    nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
   coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167
 */
class MaxCoins
{
    // _dp[left][right]
    int _dp[501][501];
public:
    int maxCoins(vector<int>& nums) {
        size_t n = nums.size() + 2;
        vector<int> i_nums;
        size_t i, k, left, right;
        i_nums.push_back(1);
        for (i = 0; i < nums.size(); ++i) {
            i_nums.push_back(nums[i]);
        }
        i_nums.push_back(1);
        for (i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                _dp[i][j] = 0;
            }
        }
        
        for (k = 2; k < n; ++k) {
            for (left = 0; left < (n - k); ++left) {
                right = left + k;
                for (i = left + 1; i < right; ++i) {
                    _dp[left][right] = max(_dp[left][right],
                        i_nums[left] * i_nums[i] * i_nums[right] + _dp[left][i] + _dp[i][right]
                    );
                }
            }
        }
        
        return _dp[0][n - 1];
    }
};

class MaxCoinsTest : public testing::Test
{
};

TEST_F(MaxCoinsTest, MCT1)
{
    MaxCoins mc;
    vector<int> d = {3, 1, 5, 8};
    EXPECT_EQ(mc.maxCoins(d), 167);
}


class SearchMatrix {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 0) return false;
        int m = static_cast<int>(matrix.size());
        int n = static_cast<int>(matrix[0].size());
        int i = 0;
        while (i < m && i < n) {
            if (matrix[i][i] == target) return true;
            if (matrix[i][i] < target) ++i;
            else {
                int j;
                int k;
                int k_bound = m;
                // could add binary search to speed up
                for (k = i; k < k_bound; ++k) {
                    for (j = i - 1; j >= 0; --j) {
                        // search current row
                        if (matrix[k][j] == target) return true;
                        if (matrix[k][j] < target) break;
                    }
                }
                k_bound = n;
                for (k = i; k < k_bound; ++k) {
                    for (j = i - 1; j >= 0; --j) {
                        // search current column
                        if (matrix[j][k] == target) return true;
                        if (matrix[j][k] < target) break;
                    }
                }
                
                return false;
            }
        }
        
        if (m > n) {
            i = n - 1;
            int j = n - 1;
            for (; j < m; ++j) {
                if (matrix[j][i] == target) return true;
                if (matrix[j][i] > target) {
                    for (int k = j - 1; k >= 0; --k) {
                        if (matrix[j][k] == target) return true;
                        if (matrix[j][k] < target) break;
                    }
                    return false;
                }
            }
        } else if (m < n) {
            i = m - 1;
            int j = m - 1;
            for (; j < n; ++j) {
                if (matrix[i][j] == target) return true;
                if (matrix[i][j] > target) {
                    for (int k = i - 1; k >= 0; --k) {
                        if (matrix[k][j] == target) return true;
                        if (matrix[k][j] < target) break;
                    }
                    return false;
                }
            }
        }
        
        return false;
    }
};

class SearchMatrixTest : public testing::Test
{
};

TEST_F(SearchMatrixTest, SMT1) {
    SearchMatrix sm;
    vector<vector<int>> matrix = {{1, 3, 5}};
    EXPECT_FALSE(sm.searchMatrix(matrix, 4));
    matrix = {
        {1,2,3,4,5},
        {6,7,8,9,10},
        {11,12,13,14,15},
        {16,17,18,19,20},
        {21,22,23,24,25}
    };
    EXPECT_TRUE(sm.searchMatrix(matrix, 15));
    matrix = {
        {2,5},
        {2,8},
        {7,9},
        {7,11},
        {9,11}
    };
    EXPECT_TRUE(sm.searchMatrix(matrix, 7));
}

class ReversePolandNotation {
public:
    bool is_number(const std::string& s) {
        int start = 0;
        if (s[start] == '+' || s[start] == '-') { 
            if (s.size() == 1) return false;
            start += 1;
        }
        for (; start < s.size(); ++start) {
            if (!isdigit(s[start])) return false;
        }
        return true;
    }
    int evalRPN(vector<string>& tokens) {
        int val;
        stack<int> num_stack;
        for (int i = 0; i < tokens.size(); ++i) {
            if (is_number(tokens[i])) {
                stringstream(tokens[i]) >> val;
                num_stack.push(val);
            }
            else {
                switch (tokens[i][0]) {
                    case '*':
                        {
                            int a = num_stack.top(); num_stack.pop();
                            int b = num_stack.top(); num_stack.pop();
                            num_stack.push(a*b);
                            break;
                        }
                    case '+':
                        {
                            int a = num_stack.top(); num_stack.pop();
                            int b = num_stack.top(); num_stack.pop();
                            num_stack.push(a+b);
                            break;
                        }
                    case '-':
                        {
                            int a = num_stack.top(); num_stack.pop();
                            int b = num_stack.top(); num_stack.pop();
                            num_stack.push(b-a);
                            break;
                        }
                    case '/':
                        {
                            int a = num_stack.top(); num_stack.pop();
                            int b = num_stack.top(); num_stack.pop();
                            num_stack.push(b/a);
                            break;
                        }
                }
            }
        }
        if (!num_stack.empty()) return num_stack.top();
        return 0;
    }
};

class ReversePolandNotationTest : public testing::Test
{
};

TEST_F(ReversePolandNotationTest, RPNT1) {
    ReversePolandNotation rpn;
    vector<string> rpnv = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};
    EXPECT_EQ(rpn.evalRPN(rpnv), 22);
}

class FullPermutation {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        
        permuteNums(res, nums, 0, nums.size());
        
        return res;
    }
    void permuteNums(vector<vector<int>>& res, vector<int>& nums, size_t low, size_t high) {
        if (low == high-1) {
            res.push_back(nums);
        } else {
            for (size_t i = low; i < high; ++i) {
                swapElem(nums, i, low);
                permuteNums(res, nums, low+1, high);
                swapElem(nums, i, low);
            }
        }
    }
    void swapElem(vector<int>& nums, size_t i, size_t j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
};

class FullPermutationTest : public testing::Test
{
};

TEST_F(FullPermutationTest, FPT1) {
    vector<vector<int>> result;
    vector<int> data = {1, 2, 3};
    FullPermutation fp;
    result = fp.permute(data);
}

class RandomizedSet {
    unordered_map<int, int> _map;
    vector<int> _vec;
public:
    /** Initialize your data structure here. */
    RandomizedSet() {
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if (_map.find(val) != _map.end()) return false;
        _map[val] = static_cast<int>(_vec.size());
        _vec.push_back(val);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if (_map.find(val) == _map.end()) return false;
        int t = _vec[_vec.size() - 1];
        if (t != val) {
            _map[t] = _map[val];
            _vec[_map[val]] = t;
        }
        _vec.pop_back();
        _map.erase(val);
        return true;
    }

    /** Get a random element from the set. */
    int getRandom() {
        //srand(static_cast <unsigned int> (time(0)));
        //auto iter = next(begin(_map), rand() % _map.size());
        return _vec[rand() % _vec.size()];
    }
};

class LongestPalindrome {
public:
    string preProcess(string &s) {
        if (s.empty()) return "^$";
        string r = "^";
        for (int i = 0; i < s.size(); ++i) {
            r += '#' + s.substr(i, 1);
        }
        r += "#$";
        return r;
    }
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        string T = preProcess(s);
        int i = 0, C = 0, R = 0;
        size_t n = T.length();
        int *P = new int[n];  // c++ 11 support dynamic array
        for (i = 1; i < n - 1; ++i) {
            int i_mirror = 2*C - i;
            P[i] = (R > i) ? min(R - i, P[i_mirror]) : 0;
            while (T[i + 1 + P[i]] == T[i -  1 - P[i]]) P[i] += 1;
            if (i + P[i] > R) {
                C = i;
                R = i + P[i];
            }
        }

        int max_len = 0, center_idx = 0;
        for (int i = 1; i < n - 1; ++i) {
            if (P[i] > max_len) {
                max_len = P[i];
                center_idx = i;
            }
        }

        delete [] P;

        return s.substr((center_idx - 1 - max_len)/2, max_len);
    }
};

class LongestPalindromeTest : public testing::Test
{};

TEST_F(LongestPalindromeTest, LPT1) {
    LongestPalindrome lp;
    string data = "babad";
    EXPECT_EQ(lp.longestPalindrome(data), string("bab"));
    data = "jglknendplocymmvwtoxvebkekzfdhykknufqdkntnqvgfbahsljkobhbxkvyictzkqjqydczuxjkgecdyhixdttxfqmgksrkyvopwprsgoszftuhawflzjyuyrujrxluhzjvbflxgcovilthvuihzttzithnsqbdxtafxrfrblulsakrahulwthhbjcslceewxfxtavljpimaqqlcbrdgtgjryjytgxljxtravwdlnrrauxplempnbfeusgtqzjtzshwieutxdytlrrqvyemlyzolhbkzhyfyttevqnfvmpqjngcnazmaagwihxrhmcibyfkccyrqwnzlzqeuenhwlzhbxqxerfifzncimwqsfatudjihtumrtjtggzleovihifxufvwqeimbxvzlxwcsknksogsbwwdlwulnetdysvsfkonggeedtshxqkgbhoscjgpiel";
    cout << lp.longestPalindrome(data) << endl;
}

class MatchCoins {
    /*
       You are given coins of different denominations and a total amount
       of money amount. Write a function to compute the fewest number of
       coins that you need to make up that amount. If that amount of
       money cannot be made up by any combination of the coins,
       return -1.

        Example 1:
        coins = [1, 2, 5], amount = 11
        return 3 (11 = 5 + 5 + 1)

        Example 2:
        coins = [2], amount = 3
        return -1.

        Note:
        You may assume that you have an infinite number of each kind
        of coin.
     */
public:
    int coinChange(vector<int>& coins, int amount) {
        if (coins.empty()) return -1;
        if (amount == 0) return 0;
        vector<int> dp(amount + 1, amount + 1);  // index: amount -> value: count
        dp[0] = 0;
        sort(coins.begin(), coins.end());
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < coins.size() && coins[j] <= i; ++j) {
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
        }
        if (dp[amount] == amount + 1) return -1;
        return dp[amount];
    }
};

class MatchCoinsTest : public testing::Test
{
};

TEST_F(MatchCoinsTest, MCT1) {
    MatchCoins mc;
    vector<int> res = {1};
    EXPECT_EQ(mc.coinChange(res, 1), 1);
}

class WordSearch {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty()) return false;
        bool res = false;
        size_t n = board.size();
        size_t m = board[0].size();
        for (size_t i = 0; i < n; ++i) {
            for (size_t j = 0; j < m; ++j) {
                if (word[0] == board[i][j]) {
                    vector<vector<bool>> access_map(n, vector<bool>(m, false));
                    res = exist(board, i, j, word, 1, access_map);
                    if (res) return res;
                }
            }
        }
        return res;
    }
    
    bool exist(vector<vector<char>>& board, size_t i, size_t j, string& word, int p, vector<vector<bool>>& access_map) {
        if (p >= word.size()) return true;
        if (access_map[i][j]) return false;
        access_map[i][j] = true;
        
        bool res = false;
        
        char val = word[p];
        
        if (i >= 1 && board[i-1][j] == val && !access_map[i-1][j]) {
            res = exist(board, i-1, j, word, p+1, access_map);
            access_map[i-1][j] = false;
        }
        if (!res && j >=1 && board[i][j-1] == val && !access_map[i][j-1]) {
            res = exist(board, i, j-1, word, p+1, access_map);
            access_map[i][j-1] = false;
        }
        if (!res && i < board.size() - 1 && board[i+1][j] == val && !access_map[i+1][j]) {
            res = exist(board, i+1, j, word, p+1, access_map);
            access_map[i+1][j] = false;
        }
        if (!res && j < board[0].size() - 1 && board[i][j+1] == val && !access_map[i][j+1]) {
            res = exist(board, i, j+1, word, p+1, access_map);
            access_map[i][j+1] = false;
        }
        
        return res;
    }
};

class WordSearchTest : public testing::Test
{

};

TEST_F(WordSearchTest, WST1) {
    WordSearch ws;
    vector<vector<char>> data = {{'a', 'a'}};
    string word = "aa";
    EXPECT_TRUE(ws.exist(data, word));
    word = "aaa";
    EXPECT_FALSE(ws.exist(data, word));
    vector<vector<char>> data1(3, vector<char>(4, '0'));
    char d1[3][4] = {
        {'A','B','C','E'},
        {'S','F','E','S'},
        {'A','D','E','E'}
    };
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 4; ++j) {
            data1[i][j] = d1[i][j];
        }
    }
    word = "ABCESEEEFS";
    EXPECT_TRUE(ws.exist(data1, word));
}

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BinaryTreeSerializer {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        // Time limit exceed!!!
        if (!root) return "";
        vector<TreeNode*> t1, t2;
        t1.push_back(root);
        bool has_elem=false;
        string res;
        res += to_string(root->val);
        
        while (true) {
            t2.clear();
            for (int i = 0; i < t1.size(); ++i) {
                if (t1[i] != nullptr) {
                    if (t1[i]->left || t1[i]->right) has_elem=true;
                    t2.push_back(t1[i]->left);
                    t2.push_back(t1[i]->right);
                } else {
                    t2.push_back(nullptr);
                    t2.push_back(nullptr);
                }
            }
            
            if (has_elem) {
                has_elem = false;
                t1 = t2;
                for (int i = 0; i < t1.size(); ++i) {
                    res += ',';
                    if (t1[i]) {
                        res += to_string(t1[i]->val);
                    } else { 
                        res += '-';
                    }
                }
            } else {
                break;
            }
        }

        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) return nullptr;
        vector<string> val_list;
        int i = 0, j = 0;
        while (i < data.size()) {
            while (data[j] != ',') ++j;
            if (i != j) val_list.push_back(data.substr(i, j-i));
            i = j + 1;
            j = i;
        }
        vector<TreeNode*> node_list;
        for (int i = 0; i < val_list.size(); ++i) {
            if (val_list[i] != "-") {
                node_list.push_back(new TreeNode(atoi(val_list[i].c_str())));
            } else {
                node_list.push_back(nullptr);
            }
        }
        
        for (int i = 0; i < node_list.size(); ++i) {
            TreeNode* node = node_list[i];
            if (node) {
                int left = 2 * i + 1;
                int right = left + 1;
                if (left < node_list.size()) {
                    node->left = node_list[left];
                }
                if (right < node_list.size()) {
                    node->right = node_list[right];
                }
            }
        }
        
        return node_list[0];
    }
};

class BinaryTreeSerializerFast {
    // Format: root,left,right;
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == nullptr) return "";
        string res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front(); q.pop();
            res += to_string(node->val);
            res += ',';
            if (node->left) {
                res += to_string(node->left->val);
                q.push(node->left);
            } else {
                res += '-';
            }
            res += ',';
            if (node->right) {
                res += to_string(node->right->val);
                q.push(node->right);
            } else {
                res += '-';
            }
            res += ';';
        }
        return res;
    }

    void getThree(TreeNode* &root, TreeNode* &left, TreeNode* &right, string val) {
        int i = 0, j = 0;
        vector<string> data;
        while (i < val.size()) {
            while (val[j] != ',' && val[j] != ';') ++j;
            if (j != i) {
                data.push_back(val.substr(i, j-i));
                if (data.size() == 3) break;
            }
            i = j+1;
            j = i;
        }
        if (root == nullptr) {
            root = new TreeNode(atoi(data[0].c_str()));
        }
        left = data[1] == "-" ? nullptr : new TreeNode(atoi(data[1].c_str()));
        right = data[2] == "-" ? nullptr : new TreeNode(atoi(data[2].c_str()));
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data == "") return nullptr;
        TreeNode *root, *left, *right;
        vector<string> data_list;
        int i = 0, j = 0;
        while (i < data.size()) {
            while (data[j] != ';') ++j;
            if (j != i) {
                data_list.push_back(data.substr(i, j-i+1));
            }
            i = j+1;
            j = i;
        }
        queue<TreeNode*> q;
        TreeNode* r = nullptr;
        i = 0;
        q.push(nullptr);
        while (!q.empty() && i < data_list.size()) {
            root = q.front(); q.pop();
            getThree(root, left, right, data_list[i]);
            if (r == nullptr) {
                r = root;
            }
            root->left = left;
            root->right = right;
            if (left) q.push(left);
            if (right) q.push(right);
            ++i;
        };
        return r;
    }
};

class BinaryTreeSerializerTest : public testing::Test
{

};

TEST_F(BinaryTreeSerializerTest, BTS1) {
    BinaryTreeSerializerFast bts;
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->right->left = new TreeNode(4);
    root->right->right = new TreeNode(5);
    string serialized_str = bts.serialize(root);
    cout << serialized_str << endl;
    TreeNode *other_root = bts.deserialize(serialized_str);
    string serialized_str2 = bts.serialize(other_root);
    cout << serialized_str2 << endl;
}

class WordSubstitute {
    struct Node {
        Node() { has_elem = false; }
        unordered_map<char, Node*> children;
        bool has_elem;
    };
    Node _root;
public:
    void insert(string& word) {
        Node* root = &_root;
        for (int i = 0; i < word.size(); ++i) {
            if (root->children.count(word[i]) == 0) {
                root->children[word[i]] = new Node;
            }
            root = root->children[word[i]];
        }
        root->has_elem = true;
    }
    bool getPrefix(string& word, string& res) {
        res.clear();
        Node* root = &_root;
        for (int i = 0; i < word.size(); ++i) {
            if (root->children.count(word[i]) == 0) return false;
            res += word[i];
            root = root->children[word[i]];
            if (root->has_elem) return true;
        }
        return true;
    }
    void splitStr(string& sentence, vector<string>& words) {
        words.clear();
        int i = 0, j = 0;
        while (sentence[i] == ' ') ++i;
        j = i;
        while (j < sentence.size()) {
            while (j < sentence.size() && sentence[j] != ' ') ++j;
            if (j < sentence.size()) words.push_back(sentence.substr(i, j - i));
            else break;
            while (sentence[j] == ' ') ++j;
            i = j;
        }
        if (sentence[sentence.size() - 1] != ' ') {
            words.push_back(sentence.substr(i, sentence.size() - i));
        }
    }
    string replaceWords(vector<string>& dict, string sentence) {
        string res;
        for (int i = 0; i < dict.size(); ++i) {
            insert(dict[i]);
        }
        vector<string> words;
        splitStr(sentence, words);
        string tmp_res;
        for (int i = 0; i < words.size(); ++i) {
            if (getPrefix(words[i], tmp_res)) res += tmp_res;
            else res += words[i];
            res += ' ';
        }
        res = res.substr(0, res.size() - 1);
        return res;
    }
};

TEST(WordSubstitute, WST1) {
    WordSubstitute ws;
    vector<string> data = { "cat", "bat", "rat" };
    string res = ws.replaceWords(data, "the cattle was rattled by the battery");
    EXPECT_EQ(res, "the cat was rat by the bat");
}

class KthLargest {
    struct Node {
        Node* left;
        Node* right;
        int count;
        int val;
        Node(int v=0) {
            left = nullptr;
            right = nullptr;
            count = 1;
            val = v;
        }
    };
    int _k;
    Node* _root;
    void insert(Node* node, int num) {
        node->count += 1;
        if (node->val < num) {
            if (node->right == nullptr) {
                node->right = new Node(num);
            } else {
                insert(node->right, num);
            }
        } else {
            if (node->left == nullptr) {
                node->left = new Node(num);
            } else {
                insert(node->left, num);
            }
        }
    }
    int searchKVal(Node* root, int k) {
        if (root->right == nullptr) {
            if (k == 1) {
                return root->val;
            } else {
                return searchKVal(root->left, k-1);
            }
        } else {
            Node* right = root->right;
            if (right->count < k) {
                k -= right->count;
                if (k == 1) return root->val;
                return searchKVal(root->left, k-1);
            } else {
                return searchKVal(right, k);
            }
        }
    }
public:
    KthLargest(int k, vector<int> nums) {
        _k = k;
        if (nums.empty()) {
            _root = nullptr;
        } else {
            _root = new Node(nums[0]);
            for (int i = 1; i < nums.size(); ++i) {
                insert(_root, nums[i]);
            }
        }
        
    }
    
    int add(int val) {
        if (_root == nullptr) {
            _root = new Node(val);
        } else {
            insert(_root, val);
        }
        return searchKVal(_root, _k);
    }
};

TEST(KthLargestTest, KLT1)
{
    KthLargest* kl = new KthLargest(1, {-2});
    EXPECT_EQ(kl->add(-3), -2);
    EXPECT_EQ(kl->add(0), 0);
    EXPECT_EQ(kl->add(2), 2);
    EXPECT_EQ(kl->add(-1), 2);
    EXPECT_EQ(kl->add(4), 4);
    delete kl;
}

class LRUCache {
    struct c_node {
        c_node* prev;
        c_node* next;
        int key;
        int val;
        c_node(int k, int v) {
            key = k;
            val = v;
            prev = nullptr;
            next = nullptr;
        }
    };
    c_node* head;
    c_node* tail;
    int cap;
    int cur_cap;
    unordered_map<int, c_node*> key2node;
public:
    LRUCache(int capacity) {
        cap = capacity;
        cur_cap = 0;
        head = nullptr;
        tail = nullptr;
    }
    ~LRUCache() {
        auto iter = key2node.begin();
        while (iter != key2node.end()) {
            delete iter->second;
            ++iter;
        }
    }
    
    int get(int key) {
        if (key2node.count(key) == 0) return -1;
        c_node* n = key2node[key];
        if (head != n) {
            if (n->prev) {
                n->prev->next = n->next;
            }
            if (n->next) {
                n->next->prev = n->prev;
            }
            if (tail == n && n->prev) {
                tail = n->prev;
            }
            n->prev = nullptr;
            n->next = head;
            head->prev = n;
            head = n;
        }
        return head->val;
    }
    
    void put(int key, int value) {
        if (key2node.count(key) > 0) {
            // if key have already exist, just update it and move it to head!
            c_node* n = key2node[key];
            if (head != n) {
                if (n->prev) {
                    n->prev->next = n->next;
                }
                if (n->next) {
                    n->next->prev = n->prev;
                }
                if (tail == n && n->prev) {
                    tail = n->prev;
                }
                n->prev = nullptr;
                n->next = head;
                head->prev = n;
                head = n;
            }
            head->val = value;
            return;
        }
        if (head == nullptr) {
            head = new c_node(key, value);
            tail = head;
            key2node[key] = head;
            cur_cap=1;
        } else {
            if (cur_cap < cap) {
                c_node* n = new c_node(key, value);
                n->next = head;
                head->prev = n;
                head = n;
                key2node[key] = head;
                cur_cap += 1;
            } else {
                c_node* t_node = tail;
                tail = tail->prev;
                if (tail) tail->next = nullptr;
                else head = tail;  // just one node!
                key2node.erase(t_node->key);
                delete t_node;
                cur_cap -= 1;
                put(key, value);
            }
        }
    }
};

TEST(LRUCache, LCT1) {
    LRUCache lc(2);
    lc.put(1, 1);
    lc.put(2, 2);
    EXPECT_EQ(lc.get(1), 1);
    lc.put(3, 3);
    EXPECT_EQ(lc.get(2), -1);
    lc.put(4, 4);
    EXPECT_EQ(lc.get(1), -1);
    EXPECT_EQ(lc.get(3), 3);
    EXPECT_EQ(lc.get(4),4);
    LRUCache lc1(1);
    lc1.put(2, 1);
    EXPECT_EQ(lc1.get(2), 1);
    lc1.put(3, 2);
    EXPECT_EQ(lc1.get(2), -1);
    EXPECT_EQ(lc1.get(3), 2);
    LRUCache lc2(2);
    EXPECT_EQ(lc2.get(2), -1);
    lc2.put(2, 6);
    EXPECT_EQ(lc2.get(1), -1);
    lc2.put(1, 5);
    lc2.put(1, 2);
    EXPECT_EQ(lc2.get(1), 2);
    EXPECT_EQ(lc2.get(2), 6);
    LRUCache lc3(2);
    lc3.put(2, 1);
    lc3.put(3, 2);
    EXPECT_EQ(lc3.get(3), 2);
    EXPECT_EQ(lc3.get(2), 1);
    lc3.put(4, 3);
    EXPECT_EQ(lc3.get(2), 1);
    EXPECT_EQ(lc3.get(3), -1);
    EXPECT_EQ(lc3.get(4), 3);
}

class FindWords {
    /*
        Given a 2D board and a list of words from the dictionary, find all words in the board.

        Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

        Example:

        Input: 
        words = ["oath","pea","eat","rain"] and board =
        [
        ['o','a','a','n'],
        ['e','t','a','e'],
        ['i','h','k','r'],
        ['i','f','l','v']
        ]

        Output: ["eat","oath"]
        Note:
        You may assume that all inputs are consist of lowercase letters a-z.
    */
    struct Trie {
        unordered_map<char, Trie*> children;
        bool is_word;
        Trie() {
            is_word = false;
        }
    };
    Trie _root;
    size_t _m, _n;
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        for (int i = 0; i < words.size(); ++i) {
            insertTrie(words[i]);
        }
        set<string> res;
        _m = board.size();
        _n = board[0].size();
        for (size_t i = 0; i < _m; ++i) {
            for (size_t j = 0; j < _n; ++j) {
                vector<vector<bool>> amap(_m, vector<bool>(_n, false));
                findWord(board, i, j, "", res, amap);
            }
        }
        vector<string> r;
        for (auto iter = res.begin(); iter != res.end(); ++iter) {
            r.push_back(*iter);
        }
        //sort(res.begin(), res.end());
        return r;
    }
    void findWord(vector<vector<char>>& board, size_t i, size_t j, string val, set<string>& res, vector<vector<bool>>& amap) {
        val += board[i][j];
        amap[i][j] = true;
        if (hasWord(val)) {
            res.insert(val);
        }
        else if (!hasPrefix(val)) {
            amap[i][j] = false;
            return;
        }
        if (i > 0 && !amap[i-1][j]) {
            findWord(board, i-1, j, val, res, amap);
        }
        if (i < _m-1 && !amap[i+1][j]) {
            findWord(board, i+1, j, val, res, amap);
        }
        if (j > 0 && !amap[i][j-1]) {
            findWord(board, i, j-1, val, res, amap);
        }
        if (j < _n-1 && !amap[i][j+1]) {
            findWord(board, i, j+1, val, res, amap);
        }
        amap[i][j] = false;
    }
    void insertTrie(string& word) {
        Trie* root = &_root;
        for (int i = 0; i < word.size(); ++i) {
            if (root->children.count(word[i]) == 0) {
                root->children[word[i]] = new Trie;
            }
            root = root->children[word[i]];
        }
        root->is_word = true;
    }
    bool hasWord(string word) {
        Trie* root = &_root;
        for (int i = 0; i < word.size(); ++i) {
            if (root->children.count(word[i]) == 0) {
                return false;
            }
            root = root->children[word[i]];
        }
        return root->is_word;
    }
    bool hasPrefix(string word) {
        Trie* root = &_root;
        for (int i = 0; i < word.size(); ++i) {
            if (root->children.count(word[i]) == 0) {
                return false;
            }
            root = root->children[word[i]];
        }
        return true;
    }
};

TEST(FindWordsTest, FWT1) {
    FindWords fw;
    vector<vector<char>> board = {{'a','b'},{'a','a'}};
    vector<string> words = {"aba","baa","bab","aaab","aaa","aaaa","aaba"};
    vector<string> r = fw.findWords(board, words);
    vector<string> rt = {"aaa","aaab","aaba","aba","baa"};
    EXPECT_EQ(r, rt);
}

class RemoveInvalidParentheses {
    /*
        Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

        Note: The input string may contain letters other than the parentheses ( and ).

        Example 1:

        Input: "()())()"
        Output: ["()()()", "(())()"]
        Example 2:

        Input: "(a)())()"
        Output: ["(a)()()", "(a())()"]
        Example 3:

        Input: ")("
        Output: [""]
     */
public:
// The following solution is too slow!
    vector<string> removeInvalidParentheses(string s) {
        if (s.empty()) return {""};
        set<string> res;
        findPara(s, "", 0, res);
        vector<string> rr;
        for (auto iter = res.begin(); iter != res.end(); ++iter) {
            rr.push_back(*iter);
        }
        return rr;
    }
    void findPara(string s, string tmp, int i, set<string>& res) {
        while (i < s.size() && s[i] != '(' && s[i] != ')') {
            tmp += s[i];
            ++i;
        }
        if (i >= s.size()) {
            // judge whether tmp is valid!
            if (!res.empty() && tmp.size() < res.begin()->size()) return;
            stack<char> sc;
            bool r = true;
            for (int i = 0; i < tmp.size(); ++i) {
                if (tmp[i] == '(') {
                    sc.push(tmp[i]);
                } else if (tmp[i] == ')') {
                    if (sc.empty()) {
                        r = false;
                        break;
                    }
                    sc.pop();
                }
            }
            if (r && sc.empty()) {
                res.insert(tmp);
            }
        } else {
            tmp += s[i]; // add this '(' or ')'
            findPara(s, tmp, i+1, res);
            tmp.erase(tmp.size()-1);
            findPara(s, tmp, i+1, res);
        }
    }
};

TEST(RemoveInvalidParenthesesTest, RIPT1) {
    RemoveInvalidParentheses rip;
    vector<string> res = rip.removeInvalidParentheses("()())()");
    EXPECT_EQ(res, vector<string>({"(())()","()()()"}));
}

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class SortList {
public:
    ListNode * sortList(ListNode* head) {
        if (head == nullptr) return nullptr;
        ListNode* tail = head;
        ListNode* tmp = head;
        int len = 1;
        while (tmp->next) {
            tail = tmp->next;
            tmp = tmp->next;
            len += 1;
        }
        return mergeSort(head, tail, len);
    }
    ListNode* mergeSort(ListNode* head, ListNode* tail, int len) {
        if (len == 1) return head;
        if (len == 2) {
            if (head->val > tail->val) {
                head->next = tail->next;
                tail->next = head;
                return tail;
            }
            return head;
        }
        int center = len / 2;
        int tmp_c = center;
        ListNode *left_tail = head, *right_head = nullptr;
        while (--tmp_c > 0) {
            left_tail = left_tail->next;
        }
        right_head = left_tail->next;
        ListNode* l1 = mergeSort(head, left_tail, center);
        ListNode* l2 = mergeSort(right_head, tail, len - center);
        ListNode* tmp = l1;
        tmp_c = center;
        while (--tmp_c) {
            tmp = tmp->next;
        }
        tmp->next = nullptr;
        tmp = l2;
        tmp_c = len - center;
        while (--tmp_c) {
            tmp = tmp->next;
        }
        tmp->next = nullptr;
        return mergeTwoList(l1, l2);
    }
    ListNode* mergeTwoList(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;
        ListNode* head;
        if (l1->val < l2->val) {
            head = l1;
            l1 = l1->next;
        }
        else {
            head = l2;
            l2 = l2->next;
        }
        ListNode* node = head;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                node->next = l1;
                l1 = l1->next;
                node = node->next;
            }
            else {
                node->next = l2;
                l2 = l2->next;
                node = node->next;
            }
        }
        if (l1 != nullptr) node->next = l1;
        else if (l2 != nullptr) node->next = l2;
        return head;
    }
};

TEST(SortList, SLT1) {
    ListNode* head = new ListNode(4);
    ListNode* tmp = head;
    tmp->next = new ListNode(3);
    tmp = tmp->next;
    tmp->next = new ListNode(1);
    tmp = tmp->next;
    tmp->next = new ListNode(2);
    tmp = tmp->next;
    SortList sl;
    head = sl.sortList(head);
    EXPECT_EQ(head->val, 1);
    EXPECT_EQ(head->next->val, 2);
    EXPECT_EQ(head->next->next->val, 3);
    EXPECT_EQ(head->next->next->next->val, 4);
}

class BinarySearch1 {
public:
    int search(vector<int>& nums, int target) {
        if (nums.size() == 0) return -1;
        size_t left = 0, right = nums.size() - 1, mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (target == nums[mid]) return static_cast<int>(mid);
            else if (target > nums[mid]) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
};

TEST(BinarySearch1, BS1T1) {
    vector<int> d = {-1, 0, 3, 5, 9, 12};
    BinarySearch1 bs1 = BinarySearch1();
    EXPECT_EQ(bs1.search(d, 9), 4);
}

class MySqrt {
public:
    int mySqrt(int x) {
        if (x <= 1) return x;
        int left = 1, right = x - 1, mid;
        double res;
        while (left <= right) {
            mid = left + (right - left) / 2;
            res = (double)x / mid;
            if (res == mid) return mid;
            else if (res < mid) right = mid - 1;  // right is always 1 smaller than the value larger than sqrt(x)
            else left = mid + 1;
        }
        return right;
    }
};

TEST(MySqrt, MSQT1) {
    MySqrt ms = MySqrt();
    EXPECT_EQ(ms.mySqrt(4), 2);
    EXPECT_EQ(ms.mySqrt(2147395599), 46339);
}


/*

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:
Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]
Example 2:
Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]
Note:
The value k is positive and will always be smaller than the length of the sorted array.
Length of the given array is positive and will not exceed 104
Absolute value of elements in the array and x will not exceed 104

 */
class KCloserNum {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int left = 0, right = static_cast<int>(arr.size() - 1), mid, d1, d2, d3;
        vector<int> res;
        while (left + 1 < right) {
            mid = left + (right - left) / 2;
            d1 = abs(x - arr[mid - 1]);
            d2 = abs(x - arr[mid]);
            d3 = abs(x - arr[mid + 1]);
            if (d1 < d2 && d2 < d3) right = mid;
            else if (d3 < d2 && d2 < d1) left = mid;
            else {
                if (d3 == d2 && d2 == d1 && d2 > 0) {
                    bool is_ok = false;
                    int half_left = left, half_right = mid, half_mid, d;
                    while (half_left <= half_right) {
                        half_mid = half_left + (half_right - half_left) / 2;
                        d = abs(x - arr[half_mid]);
                        if (d < d2) {
                            is_ok = true;
                            right = mid;
                            break;
                        }
                        else if (d > d2) half_left = half_mid + 1;
                        else half_right = half_mid - 1;
                    }
                    if (is_ok) continue;
                    half_left = mid, half_right = right;
                    while (half_left <= half_right) {
                        half_mid = half_left + (half_right - half_left) / 2;
                        d = abs(x - arr[half_mid]);
                        if (d < d2) {
                            is_ok = true;
                            left = mid;
                            break;
                        }
                        else if (d > d2) half_right = half_mid - 1;
                        else half_left = half_mid + 1;
                    }
                    if (is_ok) continue;
                    left = mid;
                    right = mid;
                    break;
                }
                else if (d1 == d2 && d1 > 0) {
                    if (d3 > d2) right = mid;
                    else left = mid;
                } else if (d2 == d3 && d2 > 0) {
                    if (d1 < d2) right = mid;
                    else left = mid;
                } else {
                    left = mid;
                    right = mid;
                    break;
                }

            }
        }
        
        d1 = abs(x - arr[left]);
        d2 = abs(x - arr[right]);
        if (d1 >= d2) mid = right;
        else mid = left;
        res.push_back(arr[mid]);
        --k;
        left = mid - 1;
        right = mid + 1;
        while (k > 0) {
            if (left < 0 && right >= arr.size()) break;
            if (left >= 0) d1 = abs(arr[left] - x);
            else d1 = INT_MAX;
            if (right < arr.size()) d2 = abs(arr[right] - x);
            else d2 = INT_MAX;
            if (left >= 0 && d1 <= d2) {
                res.push_back(arr[left]);
                --left;
                --k;
            } else if (right < arr.size() && d1 > d2) {
                res.push_back(arr[right]);
                ++right;
                --k;
            }
        }
        sort(res.begin(), res.end());
        return res;
    }   
};

TEST(KCloserNum, KCNT1) {
    KCloserNum kcn;
    vector<int> res = {1, 2, 3, 4};
    vector<int> d = {1, 2, 3, 4, 5};
    EXPECT_EQ(kcn.findClosestElements(d, 4, -1), res);
    d = {1, 2, 2, 2, 5, 5, 5, 8, 9, 9};
    res = {1, 2, 2, 2};
    EXPECT_EQ(kcn.findClosestElements(d, 4, 0), res);
    d = {1,1,2,2,3,3,6,7,8,9,9,11,11,12,12,12,13,15,18,18,21,22,22,23,25,25,32,33,34,37,37,38,38,39,39,40,41,43,43,45,45,46,46,48,48,49,50,50,53,53,54,54,56,57,57,58,58,60,60,61,62,63,63,66,69,70,71,71,71,74,75,75,76,76,80,81,81,82,84,86,86,87,87,87,88,90,91,93,93,93,94,94,94,95,96,97,98,98,98,99};
    res = {12, 12, 13};
    EXPECT_EQ(kcn.findClosestElements(d, 3, 13), res);
}

/*
Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.

It doesn't matter what you leave beyond the returned length.
Example 2:

Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.
Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
 */
class RemoveDulicatedMoreThanTwo
{
public:
    int _k = 2;
    int removeDuplicates(vector<int>& nums) {
        int n = static_cast<int>(nums.size());
        if (n == 0 || n == 1) return n;
        int i = 0, j = 0, ii = 0, c = n, diff = 0;
        while (j <= n - 1) {
            if (nums[j] != nums[ii]) {
                if (j - ii > _k) {
                    c = c - ((j - ii) - _k);
                    i = ii - diff + _k;
                    diff += ((j - ii) - _k);
                }
                ii = j;
            }
            nums[i] = nums[j];
            ++i;
            ++j;
        }
        if ((n - ii) > _k) {
            c = c - ((n - ii) - _k);
        }
        return c;
    }
};

TEST(RemoveDuplicatedMoreThanTwoTest, RDMTTT1) {
    RemoveDulicatedMoreThanTwo rd;
    vector<int> d = {1, 1, 1, 2, 2, 2, 3};
    EXPECT_EQ(rd.removeDuplicates(d), 5);
    vector<int> res = {1, 1, 2, 2, 3};
    for (int i = 0; i < 5; ++i) {
        EXPECT_EQ(d[i], res[i]);
    }
}

/*
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example: 

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.
Follow up:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n). 
 */
class MinSubArraySlow {
public:
    int minSubArrayLen2(int sum, int s, vector<int>& nums, int i, int j) {
        if (i > j) return INT_MAX;
        if (i == j) {
            if (nums[i] >= s) return 1;
            return INT_MAX;
        }
        if (sum - nums[i] < s && sum - nums[j] < s) return j - i + 1;
        if (sum - nums[i] < s) {
            return minSubArrayLen2(sum - nums[j], s, nums, i, j-1);
        }
        else if (sum - nums[j] < s) {
            return minSubArrayLen2(sum - nums[i], s, nums, i+1, j);
        }
        else {
            return min(minSubArrayLen2(sum - nums[j], s, nums, i, j-1),
                       minSubArrayLen2(sum - nums[i], s, nums, i+1, j));
        }
    }
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = static_cast<int>(nums.size());
        if (n == 0) return 0;
        int sum = 0;
        int i = 0;
        for (i = 0; i < n; ++i) sum += nums[i];
        if (sum < s) return 0;
        if (sum == s) return n;
        i = 0;
        int j = n - 1;
        return minSubArrayLen2(sum, s, nums, i, j);
    }
};

class MinSubArray {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = static_cast<int>(nums.size());
        if (n == 0) return 0;
        int l = 0, r = 0, sum = 0;
        int max_len = INT_MAX;
        while (l < n) {
            if (r < n && sum < s) {
                sum += nums[r];
                ++r;
            } else {
                sum -= nums[l];
                ++l;
            }
            if (sum >= s) {
                max_len = min(max_len, r - l);
            }
        }
        if (max_len == INT_MAX) return 0;
        return max_len;
    }
};

TEST(MinSubArrayTest, MSAT1) {
    MinSubArray msa;
    vector<int> d = {1, 4, 4};
    EXPECT_EQ(msa.minSubArrayLen(4, d), 1);
    d = {1, 2, 3, 4, 5};
    EXPECT_EQ(msa.minSubArrayLen(11, d), 3);
    d = {2, 3, 1, 2, 4, 3};
    EXPECT_EQ(msa.minSubArrayLen(7, d), 2);
}

/*
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
 */
class NearByNumber3 {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if (nums.size() < 2) return false;
        multiset<long long> s;
        for (int i = 0; i < k && i < nums.size(); ++i) s.insert(nums[i]);
        auto i = s.begin();
        auto j = s.begin();
        ++j;
        for (; j != s.end(); ++i, ++j) {
            if ((*j) - (*i) <= t) return true;
        }
        for (int p = k; p < nums.size(); ++p) {
            i = s.lower_bound(nums[p]);
            if (i != s.end()) {
                if (abs((*i) - nums[p]) <= t) return true;
                if (i != s.begin()) {
                    --i;
                    if (abs((*i) - nums[p]) <= t) return true;
                }
            } else {
                --i;
                if (abs((*i) - nums[p]) <= t) return true;
            }
            s.erase(s.find(nums[p-k]));
            s.insert(nums[p]);
            
        }
        return false;
    }
};

TEST(NearByNumber3Test, NBNT){
    NearByNumber3 nb;
    vector<int> nums = {1, 2, 3, 1};
    EXPECT_TRUE(nb.containsNearbyAlmostDuplicate(nums, 3, 0));
    nums = {1, 5, 9, 1, 5, 9};
    EXPECT_FALSE(nb.containsNearbyAlmostDuplicate(nums, 2, 3));
    nums = {7, 2, 8};
    EXPECT_TRUE(nb.containsNearbyAlmostDuplicate(nums, 2, 1));
    nums = {-1, 2147483647};
    EXPECT_FALSE(nb.containsNearbyAlmostDuplicate(nums, 1, 2147483647));
}

/**
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4
Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6
 */
struct Point {
    int x;
    int y;
    Point() : x(0), y(0) {}
    Point(int a, int b) : x(a), y(b) {}
};

class SameLineCount {
public:
    int gcd(int x, int y) {
        if (x < y) return gcd(y, x);
        while (y != 0) {
            int r = y;
            y = x % y;
            x = r;
        }
        return x;
    }
    struct PairHash {
        size_t operator()(const pair<int, int>& rhs) const {
            return hash<int>()(rhs.first) ^ hash<int>()(rhs.second);
        }
    };
    int maxPoints(vector<Point>& points) {
        int count = 0;
        for(int i = 0; i < points.size(); ++i)
        {
            /* fix points[i]，calculate other point, get slice */
            std::unordered_map<std::pair<int, int>, int, PairHash> m;
            int cnt = 0;
            int samePointCnt = 0;
            for(int j = 0; j < points.size(); ++j)
            {
                if (j == i) continue;
                /* repeat points */
                if(points[i].x == points[j].x && points[i].y == points[j].y)
                    ++samePointCnt;
                else
                {
                    int xDiff = points[i].x - points[j].x;
                    int yDiff = points[i].y - points[j].y;
                    /* greatest common divider */
                    int g = gcd(xDiff, yDiff);
                    xDiff /= g;
                    yDiff /= g;
                    cnt = std::max(cnt, ++m[std::make_pair(xDiff, yDiff)]);
                }
            }
            count = std::max(count, cnt + samePointCnt + 1);
        }
        return count;
    }
};

TEST(SameLineCountTest, SLCT1) {
    SameLineCount slc;
    vector<Point> pl = {Point(1, 1), Point(3, 2), Point(5, 3), Point(4, 1), Point(2, 3), Point(1, 4)};
    EXPECT_EQ(slc.maxPoints(pl), 4);
}

/*
Given an encoded string, return it's decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
 */
class StringDecode {
public:
    string decodeString(string s) {
        stack<int> rc;
        stack<string> ss;
        string tmp_num, tmp_str, r;
        int level = 0, cc, j, i;
        for (i = 0; i < s.size(); ++i) {
            switch (s[i]) {
                case '0':
                case '1':
                case '2':
                case '3':
                case '4':
                case '5':
                case '6':
                case '7':
                case '8':
                case '9': {
                    tmp_num += s[i];
                    break;
                }
                case '[': {
                    ss.push(tmp_str);
                    tmp_str.clear();
                    rc.push(stoi(tmp_num));
                    tmp_num.clear();
                    ++level;
                    break;
                }
                case ']': {
                    --level;
                    cc = rc.top();
                    rc.pop();
                    string last_str = ss.top();
                    ss.pop();
                    for (j = 0; j < cc; ++j) {
                        last_str += tmp_str;
                    }
                    tmp_str = last_str;
                    if (level == 0) {
                        r += tmp_str;
                        tmp_str.clear();
                    }
                    break;
                }
                default: {
                    if (level == 0) r += s[i];
                    else tmp_str += s[i];
                    break;
                }
            }
        }
        return r;
    }
};

TEST(StringDecodeTest, SDT1) {
    StringDecode sd;
    EXPECT_EQ(sd.decodeString("3[a2[c]]"), "accaccacc");
    EXPECT_EQ(sd.decodeString("sd2[f2[e]g]i") , "sdfeegfeegi");
    EXPECT_EQ(sd.decodeString("3[z]2[2[y]pq4[2[jk]e1[f]]]ef"),
     "zzzyypqjkjkefjkjkefjkjkefjkjkefyypqjkjkefjkjkefjkjkefjkjkefef");
}

/*
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.
Example 1: 
Input:

0 0 0
0 1 0
0 0 0
Output:
0 0 0
0 1 0
0 0 0
Example 2: 
Input:

0 0 0
0 1 0
1 1 1
Output:
0 0 0
0 1 0
1 2 1
Note:
The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and right.
*/
class ZeroOneMatrix {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        size_t m = matrix.size();
        if (m == 0) return {};
        size_t n = matrix[0].size();
        queue<pair<int, int>> q;
        int i, j, val;
        pair<int, int> node;
        vector<vector<int>> res = matrix;
        for (i = 0; i < m; ++i) {
            for (j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    res[i][j] = 0;
                    q.push(make_pair(i, j));
                } else {
                    res[i][j] = INT_MAX;
                }
            }
        }
        // Why we could only iterate once?
        // For up, down, left, right directions, if we reach one elem value larger than
        // current node's value+1, then we should not check and update this direction
        // anymore because we have already accessed this node and we could not get
        // optimized value through this direction.
        // BFS
        while (!q.empty()) {
            node = q.front();
            q.pop();
            val = res[node.first][node.second] + 1;
            if (node.first > 0 && res[node.first - 1][node.second] > val) {
                res[node.first - 1][node.second] = val;
                q.push(make_pair(node.first - 1, node.second));
            }
            if (node.first < m - 1 && res[node.first + 1][node.second] > val) {
                res[node.first + 1][node.second] = val;
                q.push(make_pair(node.first + 1, node.second));
            }
            if (node.second > 0 && res[node.first][node.second - 1] > val) {
                res[node.first][node.second - 1] = val;
                q.push(make_pair(node.first, node.second - 1));
            }
            if (node.second < n - 1 && res[node.first][node.second + 1] > val) {
                res[node.first][node.second + 1] = val;
                q.push(make_pair(node.first, node.second + 1));
            }
        }
        return res;
    }
};

/*
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"
Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"
Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.
 */
class BigIntegerMutiply {
    const string _add_map[10][10] = {
      // 0     1     2     3     4     5     6     7     8     9
        "00", "01", "02", "03", "04", "05", "06", "07", "08", "09", // 0
        "01", "02", "03", "04", "05", "06", "07", "08", "09", "10", // 1
        "02", "03", "04", "05", "06", "07", "08", "09", "10", "11", // 2
        "03", "04", "05", "06", "07", "08", "09", "10", "11", "12", // 3
        "04", "05", "06", "07", "08", "09", "10", "11", "12", "13", // 4
        "05", "06", "07", "08", "09", "10", "11", "12", "13", "14", // 5
        "06", "07", "08", "09", "10", "11", "12", "13", "14", "15", // 6
        "07", "08", "09", "10", "11", "12", "13", "14", "15", "16", // 7
        "08", "09", "10", "11", "12", "13", "14", "15", "16", "17", // 8
        "09", "10", "11", "12", "13", "14", "15", "16", "17", "18", // 9
    };
    const string _mul_map[10][10] = {
      // 0     1     2     3     4     5     6     7     8     9
        "00", "00", "00", "00", "00", "00", "00", "00", "00", "00", // 0
        "00", "01", "02", "03", "04", "05", "06", "07", "08", "09", // 1
        "00", "02", "04", "06", "08", "10", "12", "14", "16", "18", // 2
        "00", "03", "06", "09", "12", "15", "18", "21", "24", "27", // 3
        "00", "04", "08", "12", "16", "20", "24", "28", "32", "36", // 4
        "00", "05", "10", "15", "20", "25", "30", "35", "40", "45", // 5
        "00", "06", "12", "18", "24", "30", "36", "42", "48", "54", // 6
        "00", "07", "14", "21", "28", "35", "42", "49", "56", "63", // 7
        "00", "08", "16", "24", "32", "40", "48", "56", "64", "72", // 8
        "00", "09", "18", "27", "36", "45", "54", "63", "72", "81", // 9
    };
public:
    string multiply(string num1, string num2) {
        string& a = num1.size() > num2.size() ? num1 : num2;
        string& b = num1.size() > num2.size() ? num2 : num1;
        int an = static_cast<int>(a.size());
        int bn = static_cast<int>(b.size());
        stack<string> ss;
        char ab, bb, cb;
        int i, j, k;
        for (i = bn-1; i >= 0; --i) {
            bb = b[i];
            string rev_s; //reverse order tmp result
            cb = 0;
            for (j = an-1; j >= 0; --j) {
                ab = a[j];
                const string& r1 = _mul_map[ab-'0'][bb-'0'];
                const string& r2 = _add_map[r1[1]-'0'][cb];
                // would not overflow
                cb = _add_map[r1[0]-'0'][r2[0]-'0'][1] - '0';
                rev_s.push_back(r2[1]);
            }
            if (cb > 0) rev_s.push_back(cb+'0');
            k = bn-1-i;
            rev_s.insert(0, k, '0');
            ss.push(rev_s);
        }
        while (ss.size() > 1) {
            string s1 = ss.top();  // s1.size() would always large or equal than s2.size()
            ss.pop();
            string s2 = ss.top();
            ss.pop();
            cb = 0;
            string s;
            for (i = 0; i < s2.size(); ++i) {
                const string& r1 = _add_map[s1[i]-'0'][s2[i]-'0'];
                const string& r2 = _add_map[r1[1]-'0'][cb];
                s.push_back(r2[1]);
                cb = _add_map[r1[0]-'0'][r2[0]-'0'][1] - '0';
            }
            for (i = static_cast<int>(s2.size()); i < s1.size(); ++i) {
                const string& r1 = _add_map[s1[i]-'0'][cb];
                s.push_back(r1[1]);
                cb = r1[0] - '0';
            }
            if (cb > 0) {
                s.push_back(cb+'0');
            }
            ss.push(s);
        }
        string r = ss.top();
        while (r.size() > 1 && r.back() == '0') r.pop_back();
        reverse(r.begin(), r.end());

        return r;
    }
};

TEST(BigIntegerMutiply, BIMT1) {
    BigIntegerMutiply bim;
    EXPECT_EQ(bim.multiply("2", "3"), "6");
    EXPECT_EQ(bim.multiply("123", "456"), "56088");
    EXPECT_EQ(bim.multiply("9133", "0"), "0");
}

/*
The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

Example 1:

Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.

00 - 0
10 - 2
11 - 3
01 - 1
Example 2:

Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
             A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
             Therefore, for n = 0 the gray code sequence is [0].
 */
class GrayCode {
public:
    vector<int> grayCode(int n) {
        // we can imagine gray code as a complete binary tree with 0 and 1 edge swap
        if (n == 0) return {0};
        size_t count = static_cast<size_t>(pow(2, n));
        vector<int> heap(2 * count-1, 0);
        int level = 1;
        heap[1] = 0;
        heap[2] = 1;
        while (level < n) {
            int hb = static_cast<int>(pow(2, level + 1)) - 1;
            int lb = static_cast<int>(pow(2, level)) - 1;
            for (int i = lb; i < hb; ++i) {
                if (i % 2 == 1) {
                    heap[(i << 1) + 1] = (heap[i] << 1);
                    heap[(i << 1) + 2] = (heap[i] << 1) + 1;
                } else {
                    heap[(i << 1) + 1] = (heap[i] << 1) + 1;
                    heap[(i << 1) + 2] = (heap[i] << 1);
                }
            }
            ++level;
        }
        return vector<int>(heap.begin()+count-1, heap.end());
    }
};

TEST(GrayCodeTest, GCT1) {
    GrayCode gc;
    vector<int> r = {0, 1, 3, 2};
    EXPECT_EQ(gc.grayCode(2), r);
}

/*
You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Example 1:
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".
Example 2:
Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation:
We can turn the last wheel in reverse to move from "0000" -> "0009".
Example 3:
Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation:
We can't reach the target without getting stuck.
Example 4:
Input: deadends = ["0000"], target = "8888"
Output: -1
Note:
The length of deadends will be in the range [1, 500].
target will not be in the list deadends.
Every string in deadends and the string target will be a string of 4 digits from the 10,000 possibilities '0000' to '9999'.

 */
class OpenTheLock {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> deadlocks(deadends.begin(), deadends.end());
        unordered_set<string> visited;
        queue<string> q;
        q.push("0000");
        if (deadlocks.count("0000")) return -1;
        int res = 0;
        while (!q.empty()) {
            ++res;  // step
            for (size_t k = q.size(); k > 0; --k) {
                string s = q.front();
                q.pop();
                for (int i = 0; i < s.size(); ++i) {
                    // brute force search
                    string s1 = s;
                    string s2 = s;
                    s1[i] = s[i] == '9' ? '0' : s[i] + 1;
                    s2[i] = s[i] == '0' ? '9' : s[i] - 1;
                    if (s1 == target || s2 == target) return res;
                    if (!visited.count(s1) && !deadlocks.count(s1)) q.push(s1);
                    if (!visited.count(s2) && !deadlocks.count(s2)) q.push(s2);
                    visited.insert(s1);
                    visited.insert(s2);
                }
            }
            
        }
        return -1;
    }
};

TEST(OpenTheLockTest, OTLT1) {
    OpenTheLock otl;
    vector<string> d = { "0201", "0101", "0102", "1212", "2002" };
    EXPECT_EQ(otl.openLock(d, "0202"), 6);
}

/*
Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3
Example 2:

Input: [3,4,-1,1]
Output: 2
Example 3:

Input: [7,8,9,11,12]
Output: 1
Note:

Your algorithm should run in O(n) time and uses constant extra space.
 */
class FindMissingPositive {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = static_cast<int>(nums.size());
        int idx, tmp, i;
        for (i = 0; i < n; ++i) {
            if (nums[i] > 0 && nums[i] <= n && (nums[i]-1) != i) {
                idx = nums[i] - 1;
                tmp = nums[i];
                nums[i] = nums[idx];
                nums[idx] = tmp;
                //check whether it's swaping itself
                if (nums[i] != nums[idx]) --i;
                else nums[i] = 0;
            }
            else if (nums[i] > n) nums[i] = 0;
        }
        for (i = 0; i < n; ++i) {
            if (nums[i] <= 0) return i + 1;
        }
        return n + 1;
    }
};

TEST(FindMissingPositiveTest, FMPT1) {
    FindMissingPositive fmp;
    vector<int> d = { 3, 4, -1, 1 };
    EXPECT_EQ(fmp.firstMissingPositive(d), 2);
    d = { 7, 8, 9, 11, 12 };
    EXPECT_EQ(fmp.firstMissingPositive(d), 1);
    d = { 1, 1 };
    EXPECT_EQ(fmp.firstMissingPositive(d), 2);
}

class BasicCalculator {
public:
    int calculate(string s) {
        deque<int> d;
        deque<char> o;
        int v, n;
        string num;
        char last_op;
        for (int i = 0; i < s.size(); ++i) {
            switch (s[i]) {
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                num.push_back(s[i]);
                break;
            case '*':
            case '/':
            case '+':
            case '-':
                n = stol(num);
                num.clear();
                if (o.empty()) {
                    o.push_back(s[i]);
                    d.push_back(n);
                }
                else {
                    last_op = o.back();
                    if (last_op == '*') {
                        o.pop_back();
                        v = d.back(); d.pop_back();
                        d.push_back(v*n);
                    }
                    else if (last_op == '/') {
                        o.pop_back();
                        v = d.back(); d.pop_back();
                        d.push_back(v / n);
                    }
                    else {
                        d.push_back(n);
                    }
                    o.push_back(s[i]);
                }
                break;
            }
        }
        n = stol(num);
        if (!o.empty()) {
            if (o.back() == '*' || o.back() == '/') {
                last_op = o.back();
                o.pop_back();
                v = d.back();
                d.pop_back();
                switch (last_op) {
                case '*':
                    d.push_back(v*n);
                    break;
                default:
                    d.push_back(v / n);
                    break;
                }
            }
            else d.push_back(n);
        }
        else return n;
        n = d.front(); d.pop_front();
        while (!o.empty()) {
            v = d.front(); d.pop_front();
            last_op = o.front(); o.pop_front();
            switch (last_op) {
            case '+':
                n = n + v;
                break;
            default:
                n = n - v;
                break;
            }
        }
        return n;
    }
};

TEST(BasicCalculatorTest, BCT1) {
    BasicCalculator bc;
    EXPECT_EQ(bc.calculate("1*2-3/4+5*6-7*8+9/10"), -24);
    EXPECT_EQ(bc.calculate("0"), 0);
    EXPECT_EQ(bc.calculate("282-1*2*13-30-2*2*2/2-95/5*2+55+804+3024"), 4067);
}

class MedianFinder {
    vector<int> _stream;
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }

    void addNum(int num) {
        // not a great solution, use min max heap instead
        _stream.push_back(num);
        int tmp;
        for (size_t i = _stream.size() - 1; i > 0 && _stream[i - 1] > _stream[i]; --i) {
            tmp = _stream[i];
            _stream[i] = _stream[i - 1];
            _stream[i - 1] = tmp;
        }
    }

    double findMedian() {
        size_t n = _stream.size();
        if (n == 0) return 0;
        if (n % 2) {
            n = n / 2;
            return _stream[n];
        }
        n = n / 2;
        return (_stream[n] + _stream[n - 1]) / 2.0;
    }
};

/*
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example,
[2,3,4], the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) - Add a integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.


Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2


Follow up:

If all integer numbers from the stream are between 0 and 100, how would you optimize it?
If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?
 */
class MedianFinderMinMaxHeap {
    priority_queue<int, vector<int>, less<int>> _max;
    priority_queue<int, vector<int>, greater<int>> _min;
public:
    /** initialize your data structure here. */
    MedianFinderMinMaxHeap() {

    }

    void addNum(int num) {
        if (_max.size() == 0 && _min.size() == 0) {
            _max.push(num);
            return;
        }
        if (_max.size() > _min.size()) {
            if (num < _max.top()) {
                _max.push(num);
                num = _max.top();
                _max.pop();
            }
            _min.push(num);
        }
        else if (_min.size() > _max.size()) {
            if (num > _min.top()) {
                _min.push(num);
                num = _min.top();
                _min.pop();
            }
            _max.push(num);
        }
        else {
            if (num < _max.top()) {
                _max.push(num);
            }
            else {
                _min.push(num);
            }
        }
    }

    double findMedian() {
        if (_max.size() < 1 && _min.size() < 1) return 0;
        if (_max.size() == _min.size()) return (_max.top() + _min.top()) / 2.0;
        else if (_max.size() > _min.size()) return _max.top();
        else return _min.top();
    }
};

TEST(MedianFinderTest, MFT1) {
    MedianFinder mf;
    mf.addNum(1);
    mf.addNum(2);
    EXPECT_EQ(mf.findMedian(), 1.5);
    mf.addNum(3);
    EXPECT_EQ(mf.findMedian(), 2);
}

/*
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
 */
class LongestConsecutive {
public:
    int longestConsecutive(vector<int>& nums) {
        // to extract global information of the whole array, we can use set to store this array
        // and check items' exisitence
        unordered_set<int> s(nums.begin(), nums.end());
        int res = 0, pre, nxt;
        for (int i = 0; i < nums.size(); ++i) {
            if (!s.count(nums[i])) continue;
            pre = nums[i];
            nxt = nums[i] + 1;
            while (s.count(pre)) {
                s.erase(pre);
                --pre;
            }
            while (s.count(nxt)) {
                s.erase(nxt);
                ++nxt;
            }
            if (res < (nxt - pre - 1)) {
                res = nxt - pre - 1;
            }
        }
        return res;
    }
};

TEST(LongestConsecutiveTest, LCT) {
    LongestConsecutive lc;
    vector<int> d = { 100, 4, 200, 1, 3, 2 };
    EXPECT_EQ(lc.longestConsecutive(d), 4);
}

/*
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:

If there is no such window in S that covers all characters in T, return the empty string "".
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
 */
class MinWindowStr {
public:
    // good example to learn sliding window method
    string minWindow(string s, string t) {
        vector<int> sm(256, 0), tm(256, 0);
        for (int i = 0; i < t.size(); ++i) {
            tm[t[i]] += 1;
        }
        int beg = -1, end, i, count = 0, start;
        for (i = 0, start = i; i < s.size(); ++i) {
            sm[s[i]] += 1;
            if (sm[s[i]] <= tm[s[i]]) ++count;
            if (count == t.size()) {
                //have already find a sub string
                while (tm[s[start]] == 0) ++start;  // move start point to an char in t
                while (sm[s[start]] > tm[s[start]]) {
                    // erase duplicated elem
                    sm[s[start]] -= 1;
                    ++start;
                }
                if (beg == -1 || (end - beg) > (i - start)) {
                    beg = start;
                    end = i;
                }
                --count;
                sm[s[start]] -= 1;
                ++start;
            }
        }
        if (beg == -1) return "";
        return s.substr(beg, end - beg + 1);
    }
};

TEST(MinWindowStrTest, MWST1) {
    MinWindowStr mw;
    EXPECT_EQ(mw.minWindow("ADOBECODEBANC", "ABC"), "BANC");
}

/*

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

Input: [10,2]
Output: "210"
Example 2:

Input: [3,30,34,5,9]
Output: "9534330"
Note: The result may be very large, so you need to return a string instead of an integer.
 */
class LargestNumber {
    struct {
        bool operator() (const string& s1, const string& s2) const {
            // wrong answer:
            /*
            for (int i = 0; i < s1.size() && i < s2.size(); ++i) {
                if (s1[i] != s2[i]) return s1[i] > s2[i];
            }
            if (s1.size() == s2.size()) return s1[0] < s2[0];
            if (s1.size() > s2.size()) {
                char a = s1[s1.size()-1];
                int i = 0;
                while (i < s2.size() - 1 && s2[i] == a) ++i;
                return a > s2[i];
                
            }
            char a = s2[s2.size()];
            int i = 0; 
            while (i < s1.size() - 1 && s1[i] == a) ++i;
            return s1[i] > a;
            */
            string a = s1 + s2;
            string b = s2 + s1;
            return a > b;
        }
    } cmp_str;
public:
    string largestNumber(vector<int>& nums) {
        vector<string> nums_str;
        for (int i = 0; i < nums.size(); ++i) {
            nums_str.push_back(to_string(nums[i]));
        }
        string s;
        sort(nums_str.begin(), nums_str.end(), cmp_str);
        for (int i = 0; i < nums_str.size(); ++i) {
            s += nums_str[i];
        }
        int i = 0;
        while (s[i] == '0' && i < s.size()-1) ++i;
        return s.substr(i, s.size() - i);
    }
};

TEST(LargestNumberTest, LNT1) {
    LargestNumber ln;
    vector<int> d = { 3, 30, 34, 5, 9 };
    EXPECT_EQ(ln.largestNumber(d), "9534330");
    d = { 824, 938, 1399, 5607, 6973, 5703, 9609, 4398, 8247 };
    EXPECT_EQ(ln.largestNumber(d), "9609938824824769735703560743981399");
    d = { 121, 12 };
    EXPECT_EQ(ln.largestNumber(d), "12121");
    d = { 1440,7548,4240,6616,733,4712,883,8,9576 };
    EXPECT_EQ(ln.largestNumber(d), "9576888375487336616471242401440");
}

/*
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like ? or *.
Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:

Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.
Example 3:

Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Example 4:

Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false
 */
class WildCardMatchDP {
public:
    bool isMatch(string s, string p) {
        size_t m = s.size();
        size_t n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int i = 0; i < n; ++i) {
            dp[0][i + 1] = (dp[0][i] && p[i] == '*');  // p[i] is the i+1-th elem of p
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                dp[i + 1][j + 1] = (dp[i][j] && (s[i] == p[j] || p[j] == '?')) ||
                    (dp[i][j + 1] && p[j] == '*') ||
                    (dp[i + 1][j] && p[j] == '*');
            }
        }
        return dp[m][n];
    }
};

TEST(WildCardMatchTest, WCMT1) {
    WildCardMatchDP wcm;
    EXPECT_TRUE(wcm.isMatch("c", "*?*"));
    EXPECT_TRUE(wcm.isMatch("aaba", "?***"));
    EXPECT_FALSE(wcm.isMatch(
        "abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb"
        ,"**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb"));
    EXPECT_TRUE(wcm.isMatch("adceb", "*a*b"));
}

/*

Given n non-negative integers representing an elevation map where the width of each bar is 1,
compute how much water it is able to trap after raining.
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
 */
class GetWater {
public:
    int trap(vector<int>& height) {
        if (height.size() <= 2) return 0;
        int n = static_cast<int>(height.size());

        int max = 0, max_idx = 0;
        for (int i = 0; i < height.size(); ++i) {  // find the max height
            if (max < height[i]) {
                max = height[i];
                max_idx = i;
            }
        }
        int sum = 0;
        int p = 0, q = n - 1, root = height[0];  // calculate from left to max height
        for (; p < max_idx; ++p) {
            if (root < height[p]) root = height[p];
            else sum += root - height[p];
        }
        root = 0;  // calculate from right to max height
        for (; q > max_idx; --q) {
            if (root < height[q]) root = height[q];
            else sum += root - height[q];
        }

        return sum;
    }
};

TEST(GetWaterTest, GWT1) {
    GetWater gw;
    vector<int> h = { 0,1,0,2,1,0,1,3,2,1,2,1 };
    EXPECT_EQ(gw.trap(h), 6);
}

class WordLenChg {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_map<string, bool> wd;
        for (auto str : wordList) {
            wd[str] = true;
        }
        if (wd.count(endWord) == 0) return 0;
        queue<string> q;
        q.push(beginWord);
        q.push(".");
        wd[beginWord] = false;
        int step = 1;
        string curr;
        char orig;
        // BFS
        while (!q.empty()) {
            curr = q.front();
            q.pop();
            if (curr != ".") {
                for (int i = 0; i < curr.size(); ++i) {
                    orig = curr[i];
                    for (char j = 'a'; j <= 'z'; ++j) {
                        if (curr[i] == j) continue;
                        curr[i] = j;
                        if (wd.count(curr) && wd[curr]) {
                            q.push(curr);
                            wd[curr] = false;
                            if (curr == endWord) return step+1;
                        }
                    }
                    curr[i] = orig;
                }
            }
            else if (!q.empty()){
                q.push(".");  // next level
                ++step;
            }
        }
        return 0;
    }
};

TEST(WordLenChgTest, WLCT1) {
    WordLenChg wlc;
    vector<string> d = { "hot","dot","dog","lot","log","cog" };
    EXPECT_EQ(wlc.ladderLength("hit", "cog", d), 5);
    d = { "hot", "dog" };
    EXPECT_EQ(wlc.ladderLength("hot", "dog", d), 0);
}

class RedundentEdge
{
int tmp[1001];
public:
    int findRoot(int *tmp, int idx) {
        while (tmp[idx] != idx) idx=tmp[idx];
        return idx;
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        if (edges.empty()) return {};
        size_t N = edges.size();
        vector<int> res(2, 0);
        int i;
        for (i = 0; i <= N; ++i) tmp[i] = i;
        for (auto& edge:edges) {
            int root1 = findRoot(tmp, edge[0]);
            int root2 = findRoot(tmp, edge[1]);
            if (root1 == root2) {
                res = edge;
                break;
            }
            tmp[root1] = root2;
        }
        return res;
    }
};

TEST(RedundentEdgeTest, RET1) {
    vector<vector<int>> edges = {{1,2},{2,3},{3,4},{1,4},{1,5}};
    RedundentEdge re;
    vector<int> res = re.findRedundantConnection(edges);
    EXPECT_EQ(res[0], 1);
    EXPECT_EQ(res[1], 4);
}

/*
In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, ..., N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] that represents a directed edge connecting nodes u and v, where u is a parent of child v.

Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.

Example 1:
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given directed graph will be like this:
  1
 / \
v   v
2-->3
Example 2:
Input: [[1,2], [2,3], [3,4], [4,1], [1,5]]
Output: [4,1]
Explanation: The given directed graph will be like this:
5 <- 1 -> 2
     ^    |
     |    v
     4 <- 3
Note:
The size of the input 2D-array will be between 3 and 1000.
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.
 */
class RedundentDirectEdge
{
/*
Type 1: no cycle, but has node with in-degree 2 (3)

[[1,2], [1,3], [2,3]]

  1
 / \
v   v
2-->3

just delete the second edge of the in-degree 2 node
  1
   \
    v
2-->3

Type 2: has cycle, without in-degree 2 node

[[1,2], [2,3], [3,4], [4,1], [1,5]]

5 <- 1 -> 2
     ^    |
     |    v
     4 <- 3

Since it has cycle, we could use Union-Find to delete the last edge to form this cycle 

Type 3: has cycle, with in-degree 2 node, at this time, the in-degree 2 node is the first node of the cycle

[[1,2],[2,3],[3,1],[1,4]]

     4
    /
   v
   1
 /  ^
v    \
2 -->3

We could only delete the first edge of the in-degree node
     4
    / ^
   v  |
   1  |
 /  ^ |
v    \|
2 --->3

*/
    int tmp[1001];
public:
    int findRoot(int *tmp, int idx) {
        while (tmp[idx] != idx) idx = tmp[idx];
        return idx;
    }
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        if (edges.empty()) return {};
        size_t N = edges.size();
        int i;
        for (i = 0; i <= N; ++i) {
            tmp[i] = 0;
        }
        vector<int> first, second;
        
        for (auto& edge:edges) {
            if (tmp[edge[1]] == 0) {
                tmp[edge[1]] = edge[0];
            } else {
                // has in-degree 2 node
                first = {tmp[edge[1]], edge[1]};  // first edge
                second = edge;  // second edge
                edge[1] = 0;  // mark this node
                break;
            }
        }
        
        for (i = 0; i <= N; ++i) {
            tmp[i] = i;
        }
        
        for (auto& edge:edges) {
            // If there is not any in-degree 2 node, just use Union-Find
            // If there is, edge[1] == 0 means to ignore the in-degree 2 node
            if (edge[1] == 0) continue;
            int root1 = findRoot(tmp, edge[0]);
            int root2 = findRoot(tmp, edge[1]);
            if (root1 == root2) {
                return first.empty() ? edge : first;
            }
            tmp[root2] = root1;
        }
        return second;
    }
};

TEST(RedundentDirectEdgeTest, RDET1) {
    vector<vector<int>> edges = {{2,1},{3,1},{4,2},{1,4}};
    RedundentDirectEdge rde;
    vector<int> res = rde.findRedundantDirectedConnection(edges);
    EXPECT_EQ(res[0], 2);
    EXPECT_EQ(res[1], 1);
}

class KthLargest2 {
    vector<int> _arr;
    int _k;
    int _n;
    int leftChild(int idx) { return (idx << 1) + 1; }
    int parent(int idx) { return (idx - 1) >> 1; }
public:
    KthLargest2(int k, vector<int> nums) {
        _k = k;
        _arr.resize(k, 0);
        _n = 0;
        for (size_t i = 0; i < nums.size(); ++i) {
            add(nums[i]);
        }
    }
    
    int add(int val) {
        if (_n < _k) {
            int idx = _n, par = parent(idx);
            while (par >= 0) {
                if (val >= _arr[par]) break;
                _arr[idx] = _arr[par];
                idx = par;
                if (idx == 0) break;
                par = parent(idx);
            }
            _arr[idx] = val;
            _n += 1;
        } else if (val > _arr[0]) {
            int idx = 0, left_child = leftChild(idx);
            while (left_child < _k) {
                if ((left_child + 1) < _k && _arr[left_child] > _arr[left_child + 1]) ++left_child;
                if (val <= _arr[left_child]) break;
                _arr[idx] = _arr[left_child];
                idx = left_child;
                left_child = leftChild(idx);
            }
            _arr[idx] = val;
        }
        int res = _arr[0];
        return res;
    }
};

TEST(KthLargestTest2, KLT1) {
    KthLargest2 kl(3, {4, 5, 8, 2});
    EXPECT_EQ(kl.add(3), 4);
    EXPECT_EQ(kl.add(5), 5);
    EXPECT_EQ(kl.add(10), 5);
    EXPECT_EQ(kl.add(9), 8);
    EXPECT_EQ(kl.add(4), 8);
}

class NetworkDelayTime
{
    struct cmp {
        bool operator()(pair<int, int> &a, pair<int, int> &b) {
            return a.second < b.second;
        }
    };
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        //static auto cmp = [](pair<int, int> &a, pair<int, int> &b) { return a.second < b.second; };
        unordered_map<int, vector<pair<int, int>>> network;
        for (auto& time:times) {
            network[time[0]].push_back(make_pair(time[1], time[2]));
        }
        queue<int> q;
        vector<int> weight(N+1, INT_MAX);
        int max_time = 0;
        q.push(K);
        weight[K] = 0;
        int i;
        while (!q.empty()) {
            vector<int> acc(N+1, false);
            // level Dijkstra
            for (i = static_cast<int>(q.size()); i > 0; --i) {
                int node = q.front();
                q.pop();
                for (auto& e:network[node]) {
                    if ((weight[node] + e.second) < weight[e.first]) {
                        weight[e.first] = weight[node] + e.second;
                        if (!acc[e.first]) {
                            // prevent multiple add at the same level
                            acc[e.first] = true;
                            q.push(e.first);
                        }
                    }
                }
            }
        }
        for (int i = 1; i <= N; ++i) {
            if (weight[i] == INT_MAX) return -1;
            if (max_time < weight[i]) max_time = weight[i];
        }
        return max_time;
        /*vector<vector<int>> network(101, vector<int>(101, -1));
        for (auto time:times) {
            network[time[0]][time[1]] = time[2];
        }
        queue<int> q;
        q.push(K);
        vector<int> weight(101, INT_MAX);
        weight[K] = 0;
        int i, j;
        while (!q.empty()) {
            vector<bool> acc(101, false);
            // multi-level
            for (i = q.size(); i > 0; --i) {
                int node = q.front();
                q.pop();
                for (j = 1; j < 101; ++j) {
                    if (network[node][j] != -1 && (weight[node] + network[node][j]) < weight[j]) {
                        weight[j] = weight[node] + network[node][j];
                        if (!acc[j]) {
                            acc[j] = true;
                            q.push(j);
                        }
                    }
                }
            }
            
        }
        
        int max_weight = 0;
        for (int i = 1; i <= N; ++i) {
            if (weight[i] == INT_MAX) return -1;
            if (max_weight < weight[i]) max_weight = weight[i];
        }
        return max_weight;*/
    }
};

TEST(NetworkDelayTimeTest, NDT1) {
    NetworkDelayTime ndt;
    vector<vector<int>> times = {{4,2,76},{1,3,79},{3,1,81},{4,3,30},{2,1,47},{1,5,61},{1,4,99},{3,4,68},{3,5,46},{4,1,6},{5,4,7},{5,3,44},{4,5,19},{2,3,13},{3,2,18},{1,2,0},{5,1,25},{2,5,58},{2,4,77},{5,2,74}};
    EXPECT_EQ(ndt.networkDelayTime(times, 5, 3), 59);
}

#endif
